package leetcode.code2045;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int secondMinimum(int n, int[][] edges, int time, int change) {
		Map<Integer, List<Integer>> ways = new HashMap<>();
		for (int[] edge : edges) {
			int a = edge[0], b = edge[1];
			List<Integer> way4a = ways.getOrDefault(a, new ArrayList<>());
			List<Integer> way4b = ways.getOrDefault(b, new ArrayList<>());
			way4a.add(b);
			way4b.add(a);
			ways.put(a, way4a);
			ways.put(b, way4b);
		}
		Integer[] f = new Integer[n + 1];
		Arrays.fill(f, Integer.MAX_VALUE);
		Integer[] s = new Integer[n + 1];
		Arrays.fill(s, Integer.MAX_VALUE);
		f[1] = 0;
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { 1, 0 });
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			List<Integer> way4cur = ways.get(cur[0]);
			int dis = cur[1];
			int next = dis + 1;
			for (Integer to : way4cur) {
				if (next < f[to]) {
					f[to] = next;
					queue.add(new int[] { to, next });
				} else if (next > f[to] && next < s[to]) {
					s[to] = next;
					queue.add(new int[] { to, next });
				}
			}

		}
		int ans = 0;
		int round = change << 1;
//		System.out.println(s[n]);
		for (int i = 0; i < s[n]; i++) {
			if (ans % round >= change) {// 得带= ，面壁思过
				ans += round - ans % round + time;
			} else {
				ans += time;
			}
		}
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(13, this.secondMinimum(5, HelpDebug.str2array1("[[1,2],[1,3],[1,4],[3,4],[4,5]]"), 3, 5));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare(11, this.secondMinimum(2, HelpDebug.str2array1("[[1,2]]"), 3, 2));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare(5, this.secondMinimum(2, HelpDebug.str2array1("[[1,2]]"), 1, 2));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
